﻿package RecursiveSearcher;

import java.util.ArrayList;
import java.util.List;

/**
 * @ClassName LC131
 * @Description 分割回文串
 * @Author ZJX
 * @Date 2024/10/23 16:20
 * @Version 1.0
 */
public class LC131 {
    List<List<String>> ret;
    List<String> path;
    public List<List<String>> partition(String s) {
        ret = new ArrayList<>();
        path = new ArrayList<>();
        dfs(s, 0);
        return ret;
    }

    private void dfs(String s, int startIndex) {
        if (startIndex == s.length()) {
            ret.add(new ArrayList<>(path));
        }
        for (int endIndex = startIndex; endIndex < s.length(); endIndex++) {
            if (isPalindrome(startIndex, endIndex, s)) {
                path.add(s.substring(startIndex, endIndex + 1)); // substring 方法  前闭后开
                dfs(s, endIndex + 1);
                path.remove(path.size() - 1);
            }
        }
    }

    private boolean isPalindrome(int left, int right, String s){
        while(left < right){
            if(s.charAt(left++)!= s.charAt(right--)){
                return false;
            }
        }
        return true;
    }
}
